package algorithm.leetcode.I1to100;

/**
 * 表格中的单词搜索,DFS
 */

public class Q79 {

    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                boolean dfsResult = dfs(board, word, new boolean[board.length][board[0].length], new StringBuilder(""), i, j);
                if (dfsResult) return true;
            }
        }

        return false;
    }

    /**
     * 格子坐标 row 和 col 比 curr 领先一步,表示当前curr下一步待尝试的位置是 row 和 col
     * 分不清的时候从上面的 exist 方法的初始条件去辨别, 开始 curr="",row col 一定是即将试探的下一个位置
     */
    private boolean dfs(char[][] board,
                        String word,
                        boolean[][] isSearched,
                        StringBuilder curr,
                        int row,
                        int col) {
        // 先判断上层添加了新char的字符串是否符合要求(由于是上层添加故一定合法)
        if (curr.length() > 0 && curr.charAt(curr.length()-1) != word.charAt(curr.length()-1)) return false;
        if (curr.toString().equals(word)) return true;

        // 再判断进入本层的前提要求
        if (row < 0 || row > board.length-1) return false;
        if (col < 0 || col > board[0].length-1) return false;
        if (isSearched[row][col]) return false;

        // 向下深入
        boolean res = false;
        isSearched[row][col] = true;
        curr.append(board[row][col]);
        for (int i = -1; i <= 1; i++) {
            if (i != 0) {
                res |= dfs(board, word, isSearched, curr, row+i, col);
                res |= dfs(board, word, isSearched, curr, row, col+i);
            }
        }
        isSearched[row][col] = false;
        curr.deleteCharAt(curr.length()-1);
        return res;
    }

}
